\section{Introduction}\label{sec:intro}

%Note: We shouldn't forget to look at this paper (SODA'12) Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph
%Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan and
%Yuan Zhou
% Added this in related work - Atish

Density is a very well studied graph property with a wide range of applications stemming from the fact that it is an excellent measure of the strength of inter-connectivity between nodes. While several variants of graph density problems and algorithms have been explored in the classical setting, there is surprisingly little work that addresses this question in the distributed computing framework. This paper focuses on decentralized algorithms for identifying dense subgraphs in dynamic networks.

% networks, in particular, on decentralized algorithms for arbitrary (perhaps dynamic) networks.

Finding dense subgraphs has received a great deal of attention in graph algorithms literature because of the robustness of the property. The density of a subgraph only gradually changes when edges come and go in a network, unlike other graph properties such as connectivity that are far more sensitive to perturbation. Density measures the {\em strength} of a set of nodes by the graph induced on them from the overall structure. The power of density lies in locally observing the strength of {\em any} set of nodes, large or small, independent of the entire network.


%\atish{All the below seem to suggest we want to do something with the dense subgraph. I think it is more important for this paper to stress the fact that finding dense subgraphs is a very well studied fundamental graph property that has received little attention in terms of distributed computation. We should avoid suggesting one specific use of the dense subgraph (since specifically in the dynamic setting this subgraph can keep changing). We should just highlight that this is an interesting algorithmic question and intuitively stress on the difficulties of quickly computing dense subgraphs (both in static and dynamic graphs) in the congest model. }
%\paragraph{Motavations} Say something to motivate the study of densest subgraph problem. Possible motivations.
%\begin{itemize}
%\item Want to use densest-at-least-k subgraph to be a backbone? But may not be a good backbone
%\item Want to make sure that the network is still dense. Want to be able to alert the admin when it's not dense anymore. (In some tasks it is ok that the whole network is not dense but we want a large part of it to be dense to guarantee a good communication; e.g., we may not need all the machine to talk to each other fast but some of them should so that those machines can carry a communication-intensive task.)
%\item Detect an unusual communication. Dense = too much communication. This could be an indicator of virus, users service failure, etc.
%\item Break the network into dense components. (``Engineering the network''.) ... Find one dense component, remove and find it again. ... Maybe our algorithm will output all components with some specified density (since we are maintaining various subgraphs of various density)?
%\item Natural computing? Biology? (Link Amitabh: {\tt http://compbio.cs.uic.edu/}. She does work on Zebra network....) Also see Leslie Valiant's work.
%\item Break into many subgraphs each of which is internally dense
%\end{itemize}

%Expansion, on the other hand measures the connection between a set of nodes and the rest of the network. Therefore, density constraints would be able to assess and better maintain the strength between specified (or all) subsets of nodes (even though there are exponential such sets) in a more robust manner.

%Amitabh, Aug 07:
Dense sugraphs often give key information about the network structure, its evolution and dynamics. To quote~\cite{GibsonKT05}:\emph{``Dense subgraph extraction is therefore a key primitive for any in-depth study of the nature of a large graph''}. Often, dense subgraphs may reveal information about community structure in otherwise sparse graphs e.g. the World Wide Web or social networks. They are good structures for studying the dynamics of a network and have been used, for example, to study link spam~\cite{GibsonKT05}. It is also possible to imagine a scenario where a dynamically evolving peer-to-peer network may want to route traffic through the densest parts of its network to ease congestion; thus, these subgraphs could form the basis of an efficient communication backbone (in combination with other subgraphs selected using appropriate centrality measures).

%Consider, for example, a distributed network that requires a small set of nodes, say {\em hubs}, that are treated as central and can be used as a backbone for communication amongst them. It is conceivable and even likely that they would incur a larger communication interaction between them, and therefore demand larger connectivity structure, lower latency, and higher resilience to failures. Therefore, a peer-to-peer network would like to retain this structure, or at least identify such nodes, even as the graph evolves over time.\danupon{Review says that this is not convincing. What should we do?}

%In such an application scenario, it would be crucial to know which nodes are most strongly connected amongst themselves.


% Not directly related to our paper---Ashwin
% In another scenario, it may be useful to just test whether the entire network that is dynamically changing is still dense. It may be required, for a variety of reasons, that the graph be dense. For instance, being able to compute the densest subgraphs of a given size constraint and identifying the associated nodes would facilitate raising an alarm if and when the required property changes with time. The nice aspect of our results is that they can capture such applications even if the requirement is not on the entire graph but only on specific size constraints on the graph. These techniques could perhaps even be useful in the future in cases where a partitioning of the graph into smaller dense components is required.

% While there are no algorithms formally presented even for the static CONGEST~\cite{peleg} model framework designed to reflect peer to peer networks,

In this paper, we expand the static CONGEST model \cite{peleg} and consider a dynamic setting where the graph edges may change continually. We present algorithms for approximating the (at least size $k$) densest subgraph in a dynamic graph model to within constant factors. Our algorithms are not only designed to compute size-constrained dense subgraphs, but also track or maintain them through time, thereby allowing the network to be aware of dense subgraphs even as the network changes. They are fully decentralized and adapt well to rapid network failures or modifications. This gives the densest subgraph problem a special status among global graph problems:
%(the problems that need $\Omega(D)$ time on static networks)
while most graph problems are hard to approximate in $o(\sqrt{n})$ time even on static distributed networks of small diameters \cite{DasSarmaHKKNPPW11,NanongkaiSP11,FrischknechtHW12}, the densest subgraph problem can be approximated in polylogarithmic time (in terms of $n$) for small $D$, even in dynamic networks.

We now explain our model for dynamic networks, define density objectives considered in this paper, and state our results.

%associated results obtained in this work.


%\paragraph{Densest subgraph on edge deletion/insertion dynamic network} Define the problem. Say roughly what edge deletion/insertion dynamic network is.
%
%\paragraph{Results.}

% Amitabh: created a new file model.tex as input to this.


\input model


%\amitabh{The line below is not too clear to me. We are not maintaining any property (we don't have a repair model), we are just discovering the dense graphs. Correct?}\\
%\amitabh{Maybe we should use both 'compute' and 'maintain': compute for the first time and maintain for maintaining the computed approximation. Making some  changes below.}
We are interested in algorithms that can compute and maintain an approximate (at-least-$k$) densest subgraph
%(e.g., diameter, connectivity, densest subgraph)
of the network at all times, after a short initialization time. We say that an algorithm can compute and maintain a solution $P$ in time $T$ if it can compute the solution in $T$ rounds and can maintain a solution at all times after time $T$, even as the network changes dynamically.


\subsection{Problem definition}

%Densest subgraph, approximating densest subgraph, etc.\atish{Amitabh, this part is still incomplete - please add the definitions in.}

%\subsection{Preliminaries}
Let $G =(V,E)$ be an undirected graph and $S \subseteq \V$ be a set of nodes. Let us define the following:

\paragraph{Graph Density}
The density of a graph $G(V, E)$ is defined as $|E|/|V|$.

\paragraph{SubGraph Density}
The density of a subgraph defined by a subset of nodes $S$ of $V(G)$ is defined as the density of the induced subgraph. We will use $\den(S)$ to denote the density of the subgraph induced by $S$. Therefore, $\den(S) = \frac{|E(S)|}{|S|}$. Here $E(S)$ is the subset of edges $(u, v)$ of $E$ where $u\in S$ and $v\in S$.  In particular, when talking about the density of a subgraph defined by a set of vertices $S$ induced on $G$, we use the notation $\den_G(S)$. We also use $\den_t(S)$ to denote $\den_{G_t}(S)$. When clear from context, we omit the subscript $G$.

%Note that our definition corresponds to that of the function $g_{S}$ in~\cite{AndersenSODA08}.\\
The problem we address in this paper is to construct distributed algorithms to discover the following:
\begin{compactitem}
\item{\bf (Approximate) Densest subgraphs:} The densest subgraph problem is to find a set $S^{*} \subseteq V$, s.t. $\den(S^{*}) = \max \den(S)$ over all $S \subseteq V$. A $\alpha$-approximate solution $S'$ will be a set $S' \subseteq V$, s.t. $\den(S') \ge \frac{\den(S^{*})}{\alpha}$.
\item {\bf (Approximate) At-least-$k$-densest subgraphs:} The densest at-least-$k$-subgraph problem is the previous problem restricted to sets of size at least $k$, i.e., to find a set $S^{k*} \subseteq V, |S^{k*}| \geq k$, s.t.\ $\den(S^{k*}) = \max \den(S)$ over all $S \subseteq V, |S| \geq k$. A $\alpha$-approximate solution $S^k$ will be a set $S^k \subseteq V, |S^k| \geq k$, s.t. $\den(S^k) \ge \frac{\den(S^{k*})}{\alpha}$.
\end{compactitem}

In the distributed setting, we require that every node knows whether it is in the solution $S'$ or $S^k$ or not. We note that the latter problem is {\sf NP}-Complete, and thus it is crucial to consider approximation algorithms. The former problem can be solved {\em exactly} in polynomial time in the centralized setting, and it is an interesting open problem whether there is an exact distributed algorithm that runs in $O(D\poly\log n)$ time, even in static networks.

\subsection{Our Results}

%\begin{theorem}
%In any edge deletion and insertion dynamic network, for any $\alpha>1$ and $k\geq D_{\max}\log_\alpha n$, we can maintain an $O(\alpha)$-approximated densest subgraph of size at least $k$ using $O(1)$-time per step.
%\end{theorem}
%
%Can we still say something if we don't have the at least $k$ constraint (I forgot)? Note that we can deal with smaller $k$ at an expense of approximation ratio as well (if we delete more node then we will finish faster). So, maybe we should state this more general theorem.
%
%
%\begin{theorem}[Another possibility]
%In any edge deletion and insertion dynamic network, for any $\alpha>1$, $\delta>1$, and $k\geq (D_{\max}\log_\alpha n)/\delta$, we can maintain a subgraph of size at least $k$ and density at least $\Omega(\delta/\alpha)$ using $O(1)$-time per step, as long as there is a subgraph of size at least $k$ and density at least $\delta$.
%\end{theorem}
%
%The second theorem gives a tradeoff between the size and density of the subgraph we want to maintain. This is a simple way to view the above theorems.

%We now state the main results of this paper.
%
%\begin{theorem}[Densest at-least-$k$ problem on static networks]
%For any $k$, we can compute %maintain
%an $O(1)$-approximated densest subgraph of size at least $k$ in $O(D\log n)$ time.
%\end{theorem}
%
%%{\bf Danupon:} I combined the statement for the Densest and Densest at least $k$ problems as they state the same thing (if we don't care the approximation ratio).
%
%%\amitabh{Need to restate the theorems below to adjust for notions of time, step and compute, maintain}
%
%\begin{theorem}[Densest at least $k$ problem on dynamic networks]
%In any edge deletion and insertion dynamic network, for any $k\geq D\log n$, we can maintain
% an $O(1)$-approximated densest subgraph of size at least $k$ using $O(1)$ time.
%\end{theorem}
%
%\begin{theorem}[Densest subgraph on dynamic networks]
%In any edge deletion and insertion dynamic network, we can maintain an $O(1)$-approximated densest subgraph of size at least $k$ using $O(1)$ time per step as long as the densest subgraph has density at least $D\log n$.
%\end{theorem}

We give approximation algorithms for the densest and at-least-$k$-densest subgraph problems which are efficient even on dynamic distributed networks. In particular, we develop an algorithm that, for a fixed constant $c$ and any $\epsilon > 0$, $(2+\epsilon)$-approximates the densest subgraph in $O(D \log_{1+\epsilon} n)$ time provided that the densest subgraph has high density, i.e., it has a density at least $(cDr\log n)/\epsilon$ (recall that $r$ and $D$ are the change rate and dynamic diameter of dynamic networks, respectively). We also develop a $(3+\epsilon)$-approximation algorithm for the at-least-$k$-densest subgraph problem with the same running time, provided that the value of the density of the at-least-$k$-densest subgraph is at least $(cDr\log n)/k\epsilon$. We state these theorems in a simplified form and some corollaries below.
Below, $\epsilon$ can be set as any arbitrarily small constant. We note again that at the end of our algorithms, every node knows whether they are in the returned subgraph or not.

\begin{theorem}
There exists a distributed algorithm that for any dynamic graph with dynamic diameter $D$ and parameter $r$ returns a subgraph at time $t$ such that, w.h.p., the density of the returned subgraph is a $(2+\epsilon)$-approximation to the density of the densest subgraph at time $t$ if the densest subgraph has density at least $\Omega(Dr\log n)$.
\end{theorem}

\begin{theorem}
There exists a distributed algorithm that for any dynamic graph with dynamic diameter $D$ and parameter $r$ returns a subgraph of size at least $k$ at time $t$ such that, w.h.p., the density of the returned subgraph is a $(3+\epsilon)$-approximation to the density of the densest at least $k$ subgraph at time $t$ if the densest at least $k$ subgraph has density at least $\Omega(Dr\log n/k)$.
\end{theorem}

%We now describe some specific corollaries. Below, $\epsilon$ can be set as any arbitrarily small constant.
We mention two special cases of these theorems informally below. We prove the most general theorem statements depending on the parameters $r$ and $D$ in Section~\ref{sec:approx}.

\begin{corollary}
Given a dynamic graph with dynamic diameter $O(\log n)$ and a rate of change $r = O(\log^{\alpha} n)$ for some constant $\alpha$ (i.e. $r$ is poly-logarithmic in $n$), there is a distributed algorithm that at any time $t$ can return, w.h.p., a $(2+\epsilon)$-approximation of densest subgraph at time $t$ if the densest subgraph has density at time $t$ at least $\Omega(\log^{\alpha +2} n)$.
\end{corollary}

\begin{corollary}
Given a dynamic graph with dynamic diameter $O(\log n)$ and a rate of change $r = O(\log^{\alpha} n)$ for some constant $\alpha$ (i.e. $r$ is poly-logarithmic in $n$), there is a distributed algorithm that at any time $t$ can return, w.h.p., a $(3+\epsilon)$-approximation of $k$-densest subgraph at time $t$ if the $k$-densest subgraph has density at time $t$ at least $\Omega(\log^{\alpha +2} n/k)$.
\end{corollary}

Our algorithms follow the main ideas of centralized approximation algorithms \cite{KS,AC,Charikar00}\danupon{We didn't mention Charikar at all in the related work!}. These centralized algorithms cannot be efficiently implemented even on static distributed networks. We show how some ideas of these algorithms can be turned into time-efficient distributed algorithms with a small increase in the approximation guarantees. Similar ideas have been independently discovered and used to obtain efficient streaming and MapReduce algorithms by Bahmani et al. \cite{BahmaniKV12}.

Notice that this is already a wide range of parameter values for which our results are interesting, since the density of densest subgraphs can be as large as $\Omega(n)$ while the diameter in peer-to-peer networks is typically $O(\log n)$, and the parameter $r$ depends on the stability of the network. A caveat, though, is that in the theorems above, $D$ refers to the flooding time of the dynamic network, and not the diameter of any specific snapshot - understanding a relationship between these quantities remains open.

Further, our general theorems also imply the following for static graphs (by simply setting $r = 0$). No such results were known in the distributed setting even for static graphs.

\begin{corollary}
%In a static distributed graph, there is an algorithm that obtains, w.h.p., $(2+\epsilon)$-approximation to the densest subgraph problem in $O(D\log n)$ rounds of the CONGEST model.
In a static graph, there is a distributed algorithm that obtains, w.h.p., $(2+\epsilon)$-approximation to the densest subgraph problem in $O(D\log n)$ rounds of the CONGEST model.
\end{corollary}

\begin{corollary}
%In a static distributed graph, there is an algorithm that obtains, w.h.p, $(3+\epsilon)$-approximation to the $k$-densest subgraph problem in $O(D\log n)$ rounds of the CONGEST model.
In a static  graph, there is a distributed  algorithm that obtains, w.h.p, $(3+\epsilon)$-approximation to the $k$-densest subgraph problem in $O(D\log n)$ rounds of the CONGEST model.

\end{corollary}

Notice that this is an unconditional guarantee for static graphs (i.e. does not require any bound on the density of the optimal) and is the first distributed algorithm for these problems in the CONGEST model.

Back to dynamic graphs, in addition to computing the $(2+\epsilon)$-approximated densest and $(3+\epsilon)$-approximated at-least-$k$-densest subgraphs, our algorithm can also {\em maintain} them {\em at all times} with high probability. This means that, at all times (except for a short initialization period), all nodes are aware of whether they are part of the approximated at-least-$k$ densest subgraphs, for all $k$.

Even though we assume that all the nodes know the value $D$, all our algorithms work if some upper-bound $D'$ of $D$ is known instead; all the algorithms and analysis work identically using $D'$ rather than $D$.

\paragraph{Organization} Our algorithms are described in Section~\ref{sec:algo} and the approximation guarantees are proved in Section~\ref{sec:approx}. We mention related work at the end of the paper in Section~\ref{sec:relatedwork}.
%
%\paragraph{Danupon:} I think that, from our discussion, the above is actually the main result. The results that Atish listed earlier are below.
%
%
%\begin{theorem}\label{thm:main1}
%Under a model where the adversary is allowed to delete/add edges such that the diameter is always at most $D$, there is a distributed algorithm that requires only $O(1 + D/\log n)$ rounds per edge-failure such that it maintains a $c$-approximate densest subgraph for constant $c=$, .
%\end{theorem}
%
%\begin{theorem}\label{thm:main1}
%Under a model where the adversary is allowed to delete/add edges such that the diameter is always at most $D$, there is a distributed algorithm that requires only $O(1 + kD/\log n)$ rounds per edge-failure such that it maintains a $c$-approximate subgraph for the densest at least $k$ problem, for a constant $c=$.
%\end{theorem}
